Deadlock is a condition characterized by two or more things waiting for related events which cannot happen. For example, it may be the condition wherein a first device occupying a first resource waits to use a second resource which is held by a second device that is waiting to use the first resource. Because neither device can proceed at this point, they are both brought to a permanent standstill. Hence it is necessary to provide either means for preventing a deadlock condition from occurring, or means of detecting and resolving the deadlock condition when it does occur.
The occurrence of a deadlock is a condition faced in multipoint data communication systems, wherein a plurality of stations, such as data links, processors, input and output devices, and storage devices, are interconnected for communication by a communication medium. In such systems it may come to pass that one station attempts to access a second station via the communication medium while the second station is attempting to access the medium. The first station cannot access the second station because the second station is busy attempting to access the medium, but the second station cannot access the medium because the medium is being used by the first station. Hence a deadlock occurs.
The prior art has attempted to solve this problem in various ways. One approach has been to prevent the possibility of occurrence of deadlock by not allowing the stations in the communication system to access each other directly, rather forcing them to communicate through some passive intermediary, such as a buffer storage area; the stations can access the buffer over the communication medium but the buffer itself is passive and not capable of accessing the medium. This approach suffers from the disadvantage that additional buffer storage circuitry must be provided in the communication system, and that the stations must be provided with the additional, often complex or time consuming capability of checking the buffer storage for the presence of communications and of selecting from those communications the ones intended for this station.
Another approach of the prior art to avoiding the occurrence of deadlock has been to allow a station to access another station only after testing the availability of all resources involved in such an access, to make sure that the access can be completed. One disadvantage of this approach is that the stations must be provided with a capability of locking to themselves the needed resources, so that a resource cannot become occupied by a second station during the time between having been checked for availability and actually being used by a first station. Not only are such mechanisms generally complex and expensive to implement, but the whole procedure of testing and locking resources before using them is very time consuming, forces other stations to wait for locked yet unused resources, and hence degrades system performance.
A third approach of the prior art to solving the deadlock problem has been to detect the occurrence of deadlock, and in response to force one of the deadlocked stations to abandon its intended course of action, backing off to give the other station priority in completing its activities. Once the priority station completes its activities, the other station starts out once more on its attempt to carry out the previously abandoned activity. This approach is wasteful because it requires one of the stations to later repeat activities which it has once already performed but which it has been forced to abandon. If the station is under program control, the abandonment of and reattempt at activities generally cannot be made transparent to the software. Rather, program execution must be interrupted, control must be transferred to special software that causes the station to abandon its activity, and control must be provided to reexecute that portion of the program which resulted in the abandoned activity. Furthermore, the one station being given priority is forced to wait while the other station carries out the abandonment and resetting of its activity. System performance is thus degraded, especially in program-controlled environments.